import java.util.ArrayList;
import java.util.Date;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Stack;
import java.util.Vector;

import soot.Body;
import soot.PhaseOptions;
import soot.Scene;
import soot.SceneTransformer;
import soot.SootClass;
import soot.SootMethod;
import soot.Unit;
import soot.jimple.toolkits.callgraph.CHATransformer;
import soot.jimple.toolkits.callgraph.CallGraph;
import soot.jimple.toolkits.callgraph.Targets;
import soot.tagkit.LineNumberTag;
import soot.tagkit.Tag;
import soot.toolkits.graph.BriefUnitGraph;
import soot.toolkits.graph.UnitGraph;

public class PathTransform extends SceneTransformer {

	private Hashtable<String, ArrayList<SootMethod>> classMethods;
	private Vector<String> files;
	private String startclassindex;
	private String startclass;
	private String startline;
	private String endclassindex;
	private String endclass;
	private String endline;
	private String startmethod;
	private String endmethod;

	public PathTransform(Vector<String> files, String startClass,
			String startLine, String endClass, String endLine) {
		this.files = files;

		this.startclassindex = startClass;
		this.startline = startLine;

		this.endclassindex = endClass;
		this.endline = endLine;

		this.classMethods = new Hashtable<String, ArrayList<SootMethod>>();
	}

	@Override
	protected void internalTransform(String phaseName, Map options) {
		CHATransformer.v().transform();
		PhaseOptions.v().setPhaseOption("tag.ln", "on");
		// find the start method and class
		// find the end method and class
		processClassInfo();
		System.out.println("startclass:" + startclass);
		System.out.println("startmethod:" + startmethod);
		System.out.println("startline:" + startline);
		System.out.println("endclass:" + endclass);
		System.out.println("endline:" + endline);
		// Get the Call Graph cg
		System.out.println("start call graph!!!!");
		CallGraph cg = Scene.v().getCallGraph();

		SootClass s = Scene.v().loadClassAndSupport(startclass);
		s.setApplicationClass();
		// SootClass e = Scene.v().loadClassAndSupport(endclass);
		// e.setApplicationClass();
		SootMethod m = s.getMethod(startmethod);
		Body b = m.retrieveActiveBody();
		// Get the CFG of the main method
		UnitGraph g = new BriefUnitGraph(b);
		PathContainer allPaths = new PathContainer(startclassindex + "::"
				+ startline, endclassindex + "::" + endline);
		StaticMethod method = getPathsFromMethod(g, cg, 0, m
				.getDeclaringClass().toString());
		allPaths.addMethod(method);
		System.out.println("basic method contains " + allPaths.size()
				+ " paths");
		if (startclass != null && endclass != null) {
			while (allPaths.hasNext()) {
				StaticNode node = allPaths.next();
				// System.out.println("current node:" + node.toString()
				// + node.isCallPoint());

				// if the current node is the end point.
				// finish the current path
				if (isEndPoint(node)) {
					allPaths.finishCurrentPath();
				}

				if (node.isCallPoint()) {
					// System.out.print("is call point");
					if ((!isRecurisive(node, cg, g, allPaths.getCurrentPath()))) {
						// System.out.println("not recurisive:" +
						// node.toString());
						StaticMethod callMethod = getMethodFromNode(node, cg,
								allPaths.getCurrentPath());
						if (callMethod.size() != 0) {
							allPaths.addMethod(callMethod);
						}
					}
				}
				if (allPaths.isEndNode()) {
					allPaths.writeCurrentPath();
					// System.out.println("is end node\n");
				}
			}
			System.out.println("there are all " + allPaths.count
					+ " static path");
		} else {
			System.err.println("start point error or end point error");
			System.exit(0);
		}
	}

	private boolean isEndPoint(StaticNode node) {
		if (node.getClassName().equals(endclass)
				&& node.getLine().equals(endline)) {
			return true;
		}
		return false;
	}

	/**
	 * get the first nodes of the node , chech if it has been appeared before if
	 * so it is a recurisive call
	 * 
	 * 
	 * @param node
	 * @param cg
	 * @param g
	 * @param path
	 * @return
	 */
	private boolean isRecurisive(StaticNode node, CallGraph cg, UnitGraph g,
			StaticPath path) {
		final String[] ALLCLASS = new String[files.size()];
		files.toArray(ALLCLASS);
		Iterator targets = new Targets(cg.edgesOutOf(node.getUnit()));
		while (targets.hasNext()) {
			SootMethod smethod = (SootMethod) targets.next();
			if (smethod.getName().equals("<clinit>"))
				continue;
			String cm = smethod.getDeclaringClass().toString();
			// only take into account application classes, excluding library classes
			for (int i = 0; i < ALLCLASS.length; i++) { 
				if (cm.equals(ALLCLASS[i])) {
					if (path.hasBeenCalled(smethod)) {
						return true;
					} else {
						path.methodCalled(smethod);
						return false;
					}
				}
			}
		}
		return false;
	}

	/***
	 * get the paths from a call node. just extend the call node
	 * 
	 * @param node
	 * @param cg
	 * @param path
	 * @return
	 */
	private StaticMethod getMethodFromNode(StaticNode node, CallGraph cg,
			StaticPath path) {
		StaticMethod method = new StaticMethod();
		final String[] ALLCLASS = new String[files.size()];
		files.toArray(ALLCLASS);
		boolean unfound = true;
		Iterator targets = new Targets(cg.edgesOutOf(node.getUnit()));
		while (targets.hasNext() && unfound) {
			SootMethod sMethod = (SootMethod) targets.next();
			String cm = sMethod.getDeclaringClass().toString();

			if (sMethod.getName().equals("<clinit>"))
				continue;
			for (int i = 0; i < ALLCLASS.length; i++) {
				if (cm.equals(ALLCLASS[i])) {
					Body body = sMethod.retrieveActiveBody();
					UnitGraph cfg = new BriefUnitGraph(body);
					method = getPathsFromMethod(cfg, cg, node.getLevel() + 1,
							cm);
					unfound = false;
					break;
				}
			}
		}
		return method;
	}

	/***
	 * check if the current unit has been called before
	 * 
	 * @param _u
	 * @param _cg
	 * @param _g
	 * @return
	 */
	public boolean isCallPoint(Unit _u, CallGraph _cg, UnitGraph _g) {
		final String[] ALLCLASS = new String[files.size()];
		files.toArray(ALLCLASS);
		Iterator targets = new Targets(_cg.edgesOutOf(_u));
		while (targets.hasNext()) {
			SootMethod smethod = (SootMethod) targets.next();
			if (smethod.getName().equals("<clinit>"))
				continue;
			String cm = smethod.getDeclaringClass().toString();
			for (int i = 0; i < ALLCLASS.length; i++) {
				if (cm.equals(ALLCLASS[i])) {
					return true;
				}
			}
		}
		return false;
	}

	private StaticMethod getPathsFromMethod(UnitGraph g, CallGraph cg,
			int level, String className) {
//		long enterTime = (new Date()).getTime();
//		System.out.println("Enter getPathsFromMethod: " + enterTime);
		StaticMethod methodFromCache = PathCache.findMethod(className, g.getBody().getMethod().getSignature());
		if( methodFromCache != null ){
			StaticMethod copyMethod = new StaticMethod();
			copyMethod.setMethodSignature(methodFromCache.getMethodSignature());
			copyMethod.setPaths( new ArrayList<StaticPath>( methodFromCache.getPaths() ) );
			return copyMethod;
		}
		
		List temp = g.getHeads();
		Unit current = (Unit) temp.get(0);

		StaticMethod method = new StaticMethod();
		Stack<StaticPath> otherPaths = new Stack<StaticPath>();
		StaticPath path = new StaticPath();
		StaticNode firstNode = new StaticNode(current, isCallPoint(current, cg,
				g), level, className);
		path.addNode(firstNode);
		otherPaths.push(path);

		while (!otherPaths.empty()) {
			path = otherPaths.pop();
			current = path.getLast().getUnit();

			// finish one path
			List succs = g.getSuccsOf(current);
			// System.out.println(ClassNameIndex.getClassNum(className) +
			// "$"
			// + ((Unit) succs.get(0)).getTags().get(0).toString());
			//
			// System.out.println(endclassindex + "%" + endline + "\n");
			if (succs.size() == 0) {
				// reach the end of one path
				method.addPath(path);
			} else {
				if (succs.size() == 1) {
					// only one success node,
					// add it to the current path
					StaticNode node = new StaticNode((Unit) succs.get(0),
							isCallPoint((Unit) succs.get(0), cg, g), level,
							className);
					path.addNode(node);
					// meet the end, no need to extend
					if ((ClassNameIndex.getClassNum(className) == Integer
							.parseInt(endclassindex))
							&& (endline.equals(((Unit) succs.get(0)).getTags()
									.get(0).toString()))) {
						method.addPath(path);
					} else {
						otherPaths.add(path);
					}
				} else {
					int succsSize = succs.size();

					for (int i = 0; i < succsSize; i++) {
						StaticNode tempNode = new StaticNode((Unit) succs
								.get(i),
								isCallPoint((Unit) succs.get(i), cg, g), level,
								className);

						if (path.contains(tempNode)) {
							continue;
						}

						StaticPath anotherPath = path.clone();
						anotherPath.addNode(tempNode);

						// find end point while extending, finish the path
						if ((ClassNameIndex.getClassNum(className) == Integer
								.parseInt(endclassindex))
								&& (endline.equals(((Unit) succs.get(i))
										.toString()))) {
							method.addPath(anotherPath);
						} else {
							otherPaths.add(anotherPath);
						}
					}
				}
			}
			// System.out.println(path.toDebugString() + "\n");
		}
		method.clearSamePath();
		// System.out.println(className + " contains " + method.size() +
		// " paths");
//		long exitTime = (new Date()).getTime();
//		System.out.println("Exit getPathsFromMethod: " + exitTime);
//		System.out.println("Time elapsed: " + (exitTime - enterTime));
		PathCache.cacheMethod(className, g.getBody().getMethod().getSignature(), method);
		return method;
	}

	private void processClassInfo() {
		// TODO Auto-generat
		Vector<String> startclasses = ClassNameIndex.getClassName(Integer
				.parseInt(startclassindex));
		Vector<String> endclasses = ClassNameIndex.getClassName(Integer
				.parseInt(endclassindex));
		processPathInfo(startclasses, endclasses, startline, endline);
	}

	private void processPathInfo(Vector<String> startclasses,
			Vector<String> endclasses, String startline, String endline) {
		processStartClass(startclasses, startline);
		processEndClass(endclasses, endline);
	}

	private void processEndClass(Vector<String> classes, String line) {
		for (int i = 0; i < classes.size(); i++) {
			Vector<String> result = getMethodandClassFromLine(line, classes
					.get(i));
			if (result.size() == 0) {
				continue;
			} else {
				this.endclass = result.get(0);
				this.endmethod = result.get(1);
				break;
			}
		}
	}

	private void processStartClass(Vector<String> classes, String line) {
		for (int i = 0; i < classes.size(); i++) {
			Vector<String> result = getMethodandClassFromLine(line, classes
					.get(i));
			if (result.size() == 0) {
				continue;
			} else {
				this.startclass = result.get(0);
				this.startmethod = result.get(1);
				break;
			}
		}
	}

	/***
	 * get the class name according to the specific line number
	 * 
	 * @param line
	 * @param className
	 * @return
	 */
	private Vector<String> getMethodandClassFromLine(String line,
			String className) {
		Vector<String> results = new Vector<String>();
		SootClass s = Scene.v().loadClassAndSupport(className);
		s.setApplicationClass();
		Iterator methodIt = s.getMethods().iterator();
		boolean found = false;
		while (methodIt.hasNext() && !found) {
			SootMethod m = (SootMethod) methodIt.next();
			if (!m.isConcrete()) {
				// abstract class , skip it
				continue;
			}
			Body b = m.retrieveActiveBody();
			// System.out.println("===============");
			// System.out.println(m.toString());

			// the first and last unit of the method
			// if the line is involved in the method.
			// the line should between the two units.
			Unit firstUnit = b.getUnits().getFirst();
			Unit lastUnit = b.getUnits().getLast();

			int firstLine = getLineFromUnit(firstUnit);
			int lastLine = getLineFromUnit(lastUnit);

//			 System.out.println(firstLine + ":" + line + ":" + lastLine);

			if (firstLine <= Integer.parseInt(line)
					&& Integer.parseInt(line) <= lastLine) {
				results.add(className);
				results.add(m.toString().substring(
						m.toString().indexOf(":") + 2,
						m.toString().length() - 1));
				
				System.out.println("##### " + m.getSignature());
				System.out.println("##### " + m.getDeclaringClass().getName());
				found = true;
			}
		}
		return results;
	}

	/***
	 * get the line number from the specific unit
	 * 
	 * @param unit
	 * @return
	 */
	private int getLineFromUnit(Unit unit) {
		for (Iterator j = unit.getTags().iterator(); j.hasNext();) {
			Tag tag = (Tag) j.next();
			if (tag instanceof LineNumberTag) {
//				byte[] value = tag.getValue();
//				int lineNumber = ((value[0] & 0xff) << 8) | (value[1] & 0xff);
				LineNumberTag lnTag = (LineNumberTag)tag;
				int lineNumber = lnTag.getLineNumber();
				return lineNumber;
			}
		}
		return -1;
	}
}
